#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double db;

#define in read()
#define pii pair<int,int>
#define fi first
#define se second
#define FILE(x) freopen(x".in","r",stdin);\
	freopen(x".out","w",stdout);
#define pb push_back

int read(){
	int x = 0,sgn = 1;char ch = getchar();
	for(;!isdigit(ch);ch = getchar()) if(ch == '-') sgn = -1;
	for(;isdigit(ch);ch = getchar()) x = (x<<1)+(x<<3)+(ch^48);
	return x*sgn;
}

const int N = 3010;

int n,m,h,t,q[N];
ll s[N],a[N],f[2][N],sum;

inline ll sq(ll x){return x*x;}

ll T(int x){return s[x];}

ll Y(int o,int x){return sq(s[x]) + f[o][x];}

ll X(int x){return s[x];}

ll slope(int o,int x,int y){return (db)(Y(o,y) - Y(o,x)) / (X(y) - X(x));}

int main (){
#ifndef ONLINE_JUDGE
	freopen("1.in","r",stdin);
#endif
	n = in,m = in;
	for(int i = 1;i <= n;i++) a[i] = in,s[i] = s[i-1] + a[i];
	memset(f,0x3f,sizeof(f)); f[0][0] = 0;
	for(int o = 0,i = 1;i <= m;i++,o^=1){
		h = 1,t = 0;
		for(int j = 1;j <= n;j++){
			while(h < t && slope(o,q[t-1],q[t]) > slope(o,q[t],j-1)) t--;
			q[++t] = j - 1;
			while(h < t && slope(o,q[h],q[h+1]) < 2 * T(j)) h++;
			f[o^1][j] = f[o][q[h]] + sq(s[j] - s[q[h]]);
		}
		if(i == m) printf("%lld\n",- s[n] * s[n] + f[o^1][n] * m);
	}
	return 0;
}//(Y(o,q[t-1]) - Y(o,q[t])) * (X(q[t] - X(j))) > (Y(o,q[t-1]-Y(

